package lc2;

//4567123

public class Ex33 {
    class Solution {
        public int search(int[] nums, int target) {
            int n = nums.length, lo = 0, hi = n - 1;
            while (lo < hi) {
                int mid = (hi - lo) / 2 + lo;
                if (nums[mid] == target) {
                    return mid;
                }
                if (nums[mid] > nums[hi]) {
                    //左区间
                    if (nums[mid] > target && target >= nums[lo]) {
                        hi = mid - 1;
                    } else {
                        lo = mid + 1;
                    }
                } else {
                    //右区间
                    if (nums[mid] < target && target <= nums[hi]) {
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;
                    }
                }
            }
            return nums[lo] == target ? lo : -1;
        }
    }
}
